As is known, data processing systems may include database systems and transactional processing systems. Such systems may be standalone systems or may be part of a distributed network such as the World Wide Web. In a distributed network such as the World Wide Web, a user request is typically first processed at a server running the application with which the user is interfacing, e.g., an application server, and then processed at a server that controls storage of data that is used to service the user request, e.g., a back-end server.
An important aspect of the performance of a back-end server of a data processing system is the speed at which requests are serviced. As a typical example for a back-end server consider the database back end at a commercial web site. For such a site, it is typically vital to provide short response times to client requests. Moreover, the bottleneck in processing customers' requests is commonly the retrieval of data from the database back end. Hence, the goal of offering short response times to clients at commercial web sites often reduces to the goal of providing short response times at the back-end server.
Providing short response times to all requests at the back-end server might not always be possible, since the server's resources are limited and might not be sufficient to provide optimal service to all requests. This problem is exacerbated by the fact that server peak loads are often orders of magnitudes higher than average loads. Provisioning the system for peak loads might therefore not be feasible, or simply too wasteful, since under normal load conditions many resources would go under-utilized.
In cases where it is not possible to provide optimal service to all requests, it is typically important to provide fast service at least to the most important requests coming into the site. In the case of the database back end at a web site, important requests could, for example, be those coming from customers who have spent large amounts of money at this web site in the past. Differences in the importance of requests can also arise from that fact that, in addition to customer requests, a database might run requests from inside the site such as, for example, requests handling basic maintenance tasks. Customer requests should generally have higher priority than these background maintenance tasks. Finally, customer requests might differ in their importance depending on the type of the requests. As an example, requests that implement customer orders might be more valuable to a commercial web site than requests that just provide services for browsing the site.
There are typically two ways of implementing functionality for prioritizing requests. One is to implement request priority by integrating the scheduler into the back-end server software, the other one is to locate an external scheduler between the application server and the back-end server.
Internal schedulers are integrated into the server code, hence, obviously the implementation of the scheduling mechanisms depends on the particular server software. Moreover, the most effective way of implementing priorities inside the server might also depend on other factors such as the hardware and the operating system, or even the workload running on the system. Another drawback of internal scheduling is its high complexity. Many types of back-end servers, e.g., database systems, have been developed over a long period of time and, as a result, include extremely complex code. Integrating the scheduler into the server requires changing this complex code. Furthermore, this work will need to be repeated for every new server software package.
External scheduling has several advantages such as increased flexibility and portability. Previous approaches in the area of back-end servers in the form of database servers have employed external scheduling mostly in the form of admission control with the goal of avoiding server overload. The main idea is to either directly monitor the degree of lock contention, e.g., by keeping track of the average time a request is blocked for locks, or to monitor response times of requests or system throughput. Previous approaches in the area of back-end servers in the form of web servers focus on providing preferred service for high priority requests in the form of faster response times, but do not offer efficient mechanisms for achieving quality of service (QoS) goals such as specific response time targets.
Thus, improved techniques are needed for scheduling requests of customers of data processing systems.